Cryptosystems include public key cryptosystems and common key cryptosystems. Public key cryptosystems use different keys for decryption and encryption. In the typical public key cryptosystems, a key (public key) for encryption is laid open to the public, and a plaintext is encrypted with this public key and sent to a receiver. A key (secret key) for decrypting the ciphertext is held as secret information that only the receiver knows, and the receiver decrypts the ciphertext with the secret key to obtain the plaintext.
Elliptic curve cryptosystem attracts attention as the public key cryptosystem in these years. Various kinds of are known as this elliptic curve cryptosystem, where an operation called scalar multiplication is used in most processings. The scalar multiplication is to compute d×P=P+P+ . . . +P (sum taken d times) from a point P on an elliptic curve called a base point and an integer d called a scalar. It is known that obtaining a scalar (a secret key) d from the base point P and the scalar multiple point d×P is infeasible in the elliptic curve cryptosystem.
Here is described ECES cryptosystem as an example of the elliptic curve cryptosystem. When a sender A has a secret key s (s is an integer) and a receiver has a secret key t (t is an integer), an elliptic curve E, a base point P (=(x,y)) set on the elliptic curve E, a public key s×P (a scalar multiple point of the secret key s of the sender A and the base point P), and a public key t×P (a scalar multiple point of the secret key t of the receiver B and the base point P) are beforehand laid open to the public.
At this time, the sender A performs a scalar multiplication s×(t×P) where s is his/her own secret key and t×P is the public key of the receiver B, obtains bit representation of its x coordinate, generates a ciphertext C of a message m by performing EOR (Exclusive OR) between the former bit representation and a bit representation of the message in a bit-to-bit fashion, and transmits it to the receiver B. The receiver B performs a scalar multiplication t×(s×P) where t is his/her own secret key and s×P is the public key of the sender A, and obtains bit representation of its x coordinate. Considering that a relational expressions×(t×P)=t×(s×p)is established, the receiver B performs EOR operation between its bit representation and bit representation of the ciphertext C to decrypt the ciphertext C in a bit-to-bit fashion, and obtains the message m. As this, the cryptosystem called ECES cryptosystem performs the encryption/decryption processing using a scalar multiplications.
One of the techniques in the field of cryptography, there is one called a cryptanalysis technique. The cryptanalysis technique is for estimating secret information such as a secret key or the like from available information such as a ciphertext. There are various kinds of cryptanalysis methods. As a technique that attracts attention in recent years among them, there is a method called a side channel attack.
The side channel attack is a method invented by Paul Kocher in 1998. The side channel attack estimates key information inside the cryptographic processor by collecting and analyzing side channel information (power consumption data, time consumption data, electromagnetic wave data, etc.) at the time that various input data is given to the cryptographic processor mounted on a smart card or the like. It is indicated that use of the side channel attack may estimate a secret key from the cryptographic processor in both the public key cryptosystem and the common key cryptosystem.
Among the side channel attacks, power analysis attack is powerful. As the power analysis attack, there are known two methods, simple power analysis (SPA; Simple Power Analysis) and differential Power analysis (DPA; Differential Power Analysis). SPA is a method of estimating a secret key from characteristics of several power consumption data of the cryptographic processor. DPA is a method of estimating a secret key by analyzing differences among a number of power consumption data.
The above SPA or DPA can be applied to the elliptic curve cryptosystem. In such case, the scalar multiplication is mostly attacked. The estimating method in detail is described in documents such as Jean-Sebastein Coron “Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems”, Cryptographic Hardware and Embedded Systems 1999 (CHES1999), Lecture Notes in Computer Science vol. 1717, Springer-Verlag, pp. 292-302, 1999 (hereinafter referred to as document “Coron99”).
Meanwhile, in the cryptographic processing of elliptic curve cryptosystem, the scalar multiplication of a point on an elliptic curve is the most time-consuming part. As the simplest method for realizing the scalar multiplication d×P, there is a binary method. As the binary method, there are a method in which the computation is performed from the most significant bit (Most Significant Bit; MSB) (binary method (MSB)) and a method in which the computation is performed from the least significant bit (Least Significant Bit; LSB) (binary method (LSB)).
Here, an example of the algorithm of the binary method (MSB) is shown as (1) Algorithm 1, and an example of the algorithm of the binary method (LSB) is shown as (2) Algorithm 2. Hereinafter, small letters (d, etc.) represent scalar values, and capital letters (P, T, etc.) represent points on an elliptic curve, unless specifically noted otherwise. Elliptic curve addition is represented as ECADD, and elliptic curve doubling is represented as ECDBL. Further, a code “^” represents a power, and a string of numerical characters sandwiched between “(” and “)2” is a digit represented in binary notation. A numerical character attached S thereto such as “S1:” or the like denotes a step number in the program example representing the algorithm.
(1) Algorithm 1 [Binary Method (MSB)]S1: T:=PS2: for i=n−2 downto 0{S3:  T:=ECDBL(T)S4:  if(d[i]==1)S5:    T:=ECADD (T,P)  ※S6:  }S7: }S8: return(T)
where, T is a temporary variable, d is an n-bit scalar value, and d[i] is the i-th LSB of d.
Considering now that the scalar multiplication d×P is performed for d=21=2^4+2^2+2^0=(0101)2. At step S1, a point P is set to a variable T. At the following steps S2 to S7, respective processes corresponding to i=3, 2, 1 and 0 are performed.
When i=3, ECDBL(T) is set to the variable T, and a value of the variable T after processed is 2×P. When i=3, d[i]=d[3]=0, thus the steps S4 to S6 are skipped.
When i=2, ECDBL(T) is set to the variable T, and a value of the variable T after processed is 4×P. When i=2, d[i]=d[2]=1, thus ECADD(T,P) is set to the variable T at step S5 and a value of the variable T after processed is 5×P.
When i=1, ECDBL(T) is set to the variable T at step S3, and a value of the variable after processed is 10×P. When i=1, d[i]=d[1]=0, thus the steps S4 to S6 are skipped.
When i=0, ECDBL(T) is set to the variable T at step S3, a value of the variable T after processed is 20×P. When i=0, d[i]=d[0]=1, thus ECADD(T,P) is set to the variable T at step S5 and a value of the variable after processed is 21×P.
The processes at the step S2 to S7 are completed as above, and a value 21×P of the variable T is outputted at the final step S8. In the binary method (MSB), the process is started with the most significant bit of the scalar value, as above.
(2) Algorithm 2 [Binary Method (LSB)]S1: T[1]:=PS2: T[0]:=0S3: for i=0 upto n−1{S4:  if(d[i]==1){S5:    T[0]:=ECADD(T[0],T[1])  ※S6:  }S7   T[1]:=ECDBL(T[1])S8: }S9: return(T[0])
where, T[0] and T[1] are temporary variables, d is an n-bit scalar value, and d[i] is the i-th LSB of d.
Considering now that the scalar multiplication d×P is performed for d=21=2^4+2^2+2^0=(10101)2, for example. At the step S1, a point P is set to a variable T[1] and a point 0 is set to a variable T[0]. At the following steps S3 to S8, processes corresponding to i=0, 1, 2, 3 and 4 are performed.
When i=0, d[i]=d[0]=1, thus ECADD(T[0], T[1]) is set to the variable T[0] at step S5, thus a value of the variable T[0] after processed is P. At the step S7, ECDBL(T[1]) is set to the variable T[1], and a value of the variable after processed is 2×P.
When i=1, d[i]=d[1]=0, thus the steps S4 to S6 are skipped. At the step S7, ECDBL(T[1]) is set to the variable T[1], and a value of the variable T[1] after processed is 4×P.
When i=2, d[i]=d[2]=1, thus ECADD(T[0], T[1]) is set to the variable T[0] at the step S5 and a value of the variable T[0] after processed is 5×P. At the step S7, ECDBL(T[1]) is set to the variable T[1], and a value of the variable T[1] after processed is 8×P.
When i=3, d[i]=d[3]=0, thus the steps S4 to S6 are skipped. At the step S7, ECDBL(T[1]) is set to the variable T[1], and a value of the variable T[1] after processed is 16×P.
When i=4, d[i]=d[0]=1, thus ECADD(T[0],T[1]) is set to the variable T[0] at the step S5 and a value of the variable T[0] after processed is 21×P. At the step S7, ECDBL(T[1]) is set to the variable T[1], and a value of the variable T[1] after processed is 32×P.
The processes at the steps S3 to S8 are completed as above, and a value 21×P of the variable T[0] is outputted at the final step S9. As this, in binary method (LSB), the process is started with the least significant bit of the scalar value.
When the above Algorithm 1 and Algorithm 2 are used for the scalar multiplication of a point, the process at the step S5 indicated by ※ is performed or not performed depending on the bit value d[i] of d. The SPA analyzes the secret key d based on this feature. From many experiments, it is known that the power waveforms observed in the ECDBL operation and the ECADD operation exhibit respective distinctive characteristics and are easily distinguished. Accordingly, by measuring the power waveforms generated during the operations of Algorithm 1 or Algorithm 2 in the processor, the secret key d can be determined in accordance with the variations of the order of ECDBL and ECADD operations and the number of occurrences of the operations determined through analysis of the waveforms.
As a countermeasure against SPA, a method called “add-and-double-always” is proposed in the document Coron99, where addition and doubling are always performed. Since ECDBL operation and ECADD operation are alternately performed, this method is secure against SPA. Examples of the algorithms in which “add-and-double-always” is applied to the above-mentioned Algorithm 1 and Algorithm 2 are shown below, as Algorithm 3 and Algorithm 4.
(3) Algorithm 3 [Binary Method (MSB,add-and-double-always)]S1: T[0]:=PS2: for i=n−2 downto 0{S3:   T[0]:=ECDBL(T[0])S4:   T[1]:=ECADD(T[0],P)S5:   T[0]:=T[d[i]]S6: }S7: return(T[0])
where, T[0] and T[1] are temporary variables, d is an n-bit scalar value, and d[i] is the i-th LBS of d.
(4) Algorithm 4 [Binary Method (LSB,add-and-double-always)]S1: T[0]:=0S2: T[2]:=PS3: for i=0 upto n−1{S4:  T[1]:=ECADD(T[0],T[2])S5:  T[2]:=ECDBL(T[2])S6:  T[0]:=T[d[i]]S7: }S8: return(T[0])
where, T[0], T[1] and T[2] are temporary variables, d is an n-bit scalar value, and d[i] is the i-th LSB of d.
Use of the above Algorithm 3 and Algorithm 4 can prevent SPA. As a method having a similar effect, a method using “Montgomery-Ladder” is proposed in T. Izu, and T. Takagi, “A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks”, Public-Key Cryptography 2002 (PKC2002), Lecture Notes in Computer Science vol. 2774, pp. 280-296, Springer-Verlag, 2002 (hereinafter, referred to as document “Izu-Takagi02).
Since “Montgomery-Ladder” always computes ECDBL and ECADD alternately in the scalar multiplication d×P, it is secure against SPA. An example of “Montgomery-Ladder” is shown as Algorithm 5.
(5) Algorithm 5 [Montgomery-Ladder]S1: T[0]:=PS2: T[1]:=ECDBL(T[0])S3: for i=n−2 downto 0{S4:  T[2]:=ECDBL(T[d[i]])S5:  T[1]:=ECADD(T[0],T[1])S6:  T[0]:=T[2−d[i]]S7:  T[1]:=T[1+d[i]]S8: }S9: return(T[0])
where, T[0], T[1] and T[2] are temporary variables, d is an n-bit scalar value, and d[i] is the i-th LBS of d.
SPA can be prevented by using Algorithms 3 to 5. However, Coron99 describes DPA for these algorithms, and shows that DPA can determine the secret key through analysis in Algorithms 3 to 5. Further, Coron99 proposes a countermeasure against DPA against Algorithms 3 to 5 by introducing representation of a point on an elliptic curve using a random number, called randomized projective coordinates (RPC).
Below, an algorithm which is formed by applying the RPC to Algorithm 3 is shown as Algorithm 3′, an algorithm which is formed by applying the RPC to Algorithm 4 is shown as Algorithm 4′, and an algorithm which is formed by applying the RPC to Algorithm 5 is shown as Algorithm 5′. Each point represented by the RPC on the elliptic curve is indicated by a variable with a prime (‘or’).
(6) Algorithm 3′ [Binary Method (MSB,add-and-double-always, RPC)]S1: T′ [2]:=RPC(P)S2: T′ [0]:=T′ [2]S3: for i=n−2 downto 0{S4:  T′ [0]:=ECDBL(T′ [0])S5:  T′ [1]:=ECADD(T′ [0],T′ [2])S6:  T′ [0]:=T′ [d[i]]S7: }S8: return(invRPC(T′ [0]))
where, T′[0], T′[1] and T′[2] are temporary variables, d is an n-bit scalar value, d[i] is the i-th LSB of d, and invRPC represents inverse transform of the RPC representation.
(7) Algorithm 4′ [Binary Method (LSB,add-and-double-always, RPC)]S1: T[0]:=0S2: T′ [2]:=RPC(P)S4: for i=0 upto n−1{S4:  T′ [1]:=ECADD(T′ [0],T′ [2])S5:  T′ [2]:=ECDBL(T′ [2])S6:  T′ [0]:=T′ [d[i]]S7: }S8: return(invRPC(T′ [0]))
where, T′[0], T′[1] and T′[2] are temporary variables, d is an n-bit scalar value, d[i] is the i-th LSB of d, and invRPC represents inverse transform of the RPC representation.
(8) Algorithm 5′ [Montgomery-Ladder, RPC]S1: T′ [0]:=RPC(P)S2: T′ [1]:=ECDBL(T′ [0])S3: for i=n−2 downto 0{S4:  T′ [2]:=ECDBL(T′ [d[i]])S5:  T′ [1]:=ECADD(T′ [0], T′ [1])S6:  T′ [0]:= T′ [2−d[i]]S7:  T′ [1]:= T′ [1+d[i]]S8: }S9: return(invRPC(T′ [0])
where, T′[0], T′[1] and T′[2] are temporary variables, d is an n-bit scalar value, d[i] is the i-th LSB of d, and invRPC represents inverse transform of the RPC representation.
As a countermeasure against DPA, there is a randomized curve (RC) method having an effect similar to that of RPC, proposed in M. Joye, and C. Tymen, “Protections against differential analysis for elliptic curve cryptography”, Cryptographic Hardware and Embedded Systems 2001 (CHES 2001), Lecture Notes in Computer Science vol. 2162, pp. 377-390, Springer-Verlag, 2001 (refer to document Joye-Tymen01).
Like RPC, RC is a countermeasure against DPA and has a random value to represent a point. The way of applying RC is the same as that of applying RPC. Shown below are an algorithm to which the RC is applied to Algorithm 3 as Algorithm 3″, an algorithm to which the RC is applied to Algorithm 4 as Algorithm 4″, and an algorithm to which the RC is applied to Algorithm 5 as Algorithm 5″. Hereinafter, each point represented by RC on the elliptic curve is indicated by a variable with a double prime (“or”).
(9) Algorithm 3″ [Binary Method (MSB,add-and-double-always, RC)]S1: T″ [2]:=RC(P)S2: T″ [0]:= T″ [2]S3: for i=n−2 downto 0{S4:  T″ [0]:=ECDBL(T″ [0])S5:  T″ [1]:=ECADD(T″ [0], T″ [2])S6:  T″ [0]:= T″ [d[i]]S7: }S8: return(invRC(T″ [0])
where, T″[0], T″[1] and T″[2] are temporary variables, d is an n-bit scalar value, d[i] is the i-th LSB of d, and invRC represents inverse transform of the RC representation.
(10) Algorithm 4″ [Binary Method (LSB,add-and-double-always, RC)S1: T″ [0]:=0S2: T″ [2]:=RC(P)S3: for i=0 upto n−1{S4:  T″ [1]:=ECADD(T″ [0], T″ [2])S5:  T″ [2]:=ECDBL(T″ [2])S6:  T″ [0]:= T″ [d[i]]S7: }S8] return(invRC(T″ [0]))
where, T″[0], T″[1] and T″[2] are temporary variables, d is an n-bit scalar value, d[i] is the i-th LSB of d, and invRC represents inverse transform of the RC representation.
(11) Algorithm 5″ [Montgomery-Ladder, RC]S1: T″ [0]=RC(P)S2: T″ [1]:=ECDBL(T″ [0])S3: for i=n−2 downto 0{S4:   T″ [2]:=ECDBL(T″ [d[i]])S5:   T″ [1]:=ECADD(T″ [0], T″ [1])S6:   T″ [0]:= T″ [2−d[i]]S7:   T″ [1]:= T″ [1+d[i]]S8: }S9: return(invRC(T″ [0]))
where, T″[0], T″[1] and T″[2] are temporary variables, d is an n-bit scalar value, d[i] is the i-th LSB of d, and invRC represents inverse transform of the RC representation.
The methods for implementing the scalar multiplication d×P include a method called a window method, other than the above-mentioned binary method (Algorithms 1 and 2), and Montgomery-Ladder (Algorithm 5). For example, in a 4-bit window method, the zeroth to 15th multiples of P are computed and resulted values are stored in a table in the initializing process, the scalar value is divided into 4-bit units (windows), whereby the scalar multiplication is performed. Shown below is an algorithm of the window method (4-bit width) as Algorithm 6.
(12) Algorithm 6 [Window Method (4-bit width)]S01: W[0]=OS02: W[1]=PS03: for i=2 upto 15{S04:  W[i]=ECADD(W[i−1],P)S05: }S06: T:=W[d[n−1,n−4]]S07: for i=n−1 downto 3 step −4{S08:   T:=ECDBL(T)S09:   T:=ECDBL(T)S10:   T:=ECDBL(T)S11:   T:=ECDBL(T)S12:   T:=ECADD(T,W[d[i,i−3]])S13: }S14: return(T)
where, d is an n-bit scalar value and it is assumed that n is a multiple of 4, d[i, i−3] is a 4-bit value of the i-th to (i−3)-th bits of d, and W[i] represents a table for the window method.
Considering now the scalar multiplication for d=21=2^4+2^2+2^0=(10101)2=(0001 0101)2. Since d is 5-bit, not a multiple of 4, 0s are padded to its higher 3 bits so that d is assumed to be 8 bits, for the sake of convenience. At this time, n=8. First, W[0]=O is set as the initial value at step S01, and W[1]=P is set at step S02. Next, steps S03 to S05 are executed for i=2, 3, . . . , and 15. At step S04, W[i]=ECADD(W[i−1],P) is set to each i. At this time, a value set to W[i] is i×P. After the processes at steps S03 to S05 are completed, W[d[n−1,n−4]]=W[d[7,4]]=W[d[0001]]=1×P is set to the variable T at step S06.
Next, processes at steps S07 to S13 are performed on i=3. At step S08, T:=ECDBL(T) is processed, and 2×P is registered to the variable T. At step 09, T:=ECDBL(T) is processed, and 4×P is registered to the variable T. At step S10, T:=ECDBL(T) is processed, and 8×P is registered to the variable T. At step S11, T:=ECDBL(T) is processed, and 16×P is registered to the variable T. At step S12, T:=ECADD(T,W[d[i, i−3]])=ECADD(T,W[0101])=ECADD(16×P,5×P)=21×P is processed, and 21×P is registered to the variable T.
As above, the processes at steps S07 to S13 are completed. Finally, a value 21×P of the variable T is outputted at step S14. As this, the window method computes the scalar multiplication d×P, using a table beforehand prepared.
When Algorithm 6 (window method) is used for the scalar multiplication of a point, there are no such operations that are performed or not performed depending on the bit value in d. Thus, generally the window method, unlike the binary method, is considered to be secure against SPA. However, the window method, like the binary method, is not secure against DPA, and can be analyzed by the technique of Coron99, but it is known that, for the window method as well as the binary method and Montgomery-Ladder, RPC and RC are effective as countermeasures against DPA. An algorithm which is formed by applying RPC to Algorithm 6 is shown below as Algorithm 6′, and an algorithm which is formed by applying RC to Algorithm 6 is also shown below as Algorithm 6″.
(13) Algorithm 6′ [Window Method (4-bit width), RPC]S01: W′ [0]=OS02: W′ [1]=RPC(P)S03: for i=2 upto 15{S04:   W′ [i]=ECADD(W′ [i−1], W′ [1])S05: }S06: T′ := W′ [d[n−1,n−4]]S07: for i=n−5 downto 0 step −4{S08:   T′ :=ECDBL(T′)S09:   T′ :=ECDBL(T′)S10:   T′ :=ECDBL(T′)S11:   T′ :=ECDBL(T′)S12:   T′ :=ECADD(T′, W′ [d[i,i−3]])S13: }S14: return(invRPC(T′))
where, d is an n-bit scalar value and it is assumed that n is a multiple of 4, d[i, i−3] is a 4-bit value of the i-th to (i−3)-th bits of d, T′ is a temporary variable, W′[i] represents a table for the window method, and invRPC represents inverse transform of the RPC representation.
(14) Algorithm 6″ [Window Method (4-bit width, RC)S01: W″ [0]=0S02: W″ [1]=RC(P)S03: for i=2 upto 15{S04:   W″ [i]=ECADD(W″ [i−1], W″ [1])S05: }S06: T″ := W″ [d[n−1,n−4]]S07: for i=n−5 downto 3 step −4{S08:   T″ :=ECDBL(T″ )S09:   T″ :=ECDBL(T″ )S10:   T″ :=ECDBL(T″ )S11:   T″ :=ECDBL(T″ )S12:   T″ :=ECADD(T″ , W″ [d[i,i−3]]S13: }S14: return(invRC(T″ ))
where, d is an n-bit scalar value and it is assumed that n is a multiple of 4, d[i, i−3] is a 4-bit value of the i-th to (i-3)-th bits of d, T is a temporary variable, W [i] represents a table for the window method, and invRC represents inverse transform of the RC representation.
Conventionally, it has been considered that the above-mentioned Algorithms 3′ to 6′ and Algorithms 3″ to 6″ provide security against both SPA and DPA. Recently, a technique for analyzing these methods has been disclosed in L. Goubin, “A Refined Power-Analysis Attack on Elliptic Curve Cryptosystem”, Public-Key Cryptography 2003 (PKC2003), Lecture Notes in Computer Science vol. 2567, Springer-Verlag, pp. 199-210, 2003 (referred to as document Goubin03).
Among points on an elliptic curve, a point whose x coordinate or y coordinate is 0 is called a special point. When the special point appears during the scalar multiplication, SPA and DPA can easily detect that such point appears as an intermediate value. The analyzing method disclosed in the document Goubin03 generates such an artificial base point that the special point appears at the end of computation for a certain d[i], and estimates the value of d[i] according to whether the special point actually appears or not. Hereinafter, an attack using the analyzing method disclosed in the document Goubin03 is referred to as a special point attack, for the sake of convenience.
The binary method and Montgomery-Ladder are not secure against the special point attack. Even when RPC or RC is used, Algorithms 3′ to 6′ and Algorithms 3″ to 6″ are not secure against the special point attack because the feature that the coordinate value becomes 0 remains.
As another countermeasure against DPA on Algorithms 3 to 6, there is an exponent-splitting method (ES) proposed in C. Clavier, and M. Joye, “Universal exponentiation algorithm—A first step towards provable SPA-resistance—”, Cryptographic Hardware and Embedded Systems 2001 (CHES2001), Lecture Notes in Computer Science vol. 2162, Springer-Verlag, pp. 300-308, 2001 (referred to as document Clavier-Joye01). This ES is a method of randomly changing the scalar value. ES divides the scaler d into d=r+(d−r) by a random number r, performs separately two scalar multiplications, r×P and (d−r)×P, adds results of the two scalar multiplications, using a feature thatr×P+(d−r)×P=d×P is established, thereby computing d×P.
For the two scalar multiplications, r×P and (d−r)×P, an algorithm resistant to another SPA/DPA is used. Against the special point attack, it is possible to defend because the scalar value is randomly changed. Shown below is an algorithm of the ES as Algorithm 7.
(15) Algorithm 7 [Exponent-splitting]S1: r:=random( )S2: T1:=scalar(r,P)S3: T2:=scalar(d−r,P)S4: T:=ECADD(T1,T2)S5: return(T)
where, random( ) is a function generating an n-bit random number, scalar (d,P) is a function for performing the scalar multiplication d×P, concretely, scalar (d,P) is calculated, using the above-mentioned Algorithms 3′ to 6′ or Algorithms 3″ to 6″, and variables r, T, T1 and T2 are temporary variables.
It can be said that ES is secure against SPA, DPA and special point attack. However, the scalar multiplication used in ES is itself a countermeasure zagainst SPA and DPA, it is thus wasteful to the apply the ES to Algorithms 3′ to 6′ or Algorithms 3″ to 6″ which have already taken countermeasures against SPA and DPA. In particularly, application of these techniques requires the operation of addition and doubling of points on the elliptic curve to be performed a larger number of times than would be the case if they were not applied, resulting in increased overhead to be processed, which is a drawback.
In the light of the above problems, an object of the present invention is to provide an elliptic curve cryptosystem apparatus, an elliptic curve cryptosystem method, an elliptic curve cryptosystem program and a computer readable recording medium storing the elliptic curve cryptosystem program, which makes it difficult to estimate secret information against the special point attack thereby to improve the security of the cryptosystem processing.
Non-patent Document 1 (Document Coron99) Jean-Sebastein Coron “Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems”, Cryptographic Hardware and Embedded Systems 1999 (CHES1999), Lecture Notes in Computer Science vol. 1717, Springer-Verlag, pp. 292-302, 1999
Non-patent Document 2 (Document Izu-Takagi02): T. Izu, and T. Takagi, “A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks”, Public-Key Cryptography 2002 (PKC2002), Lecture Notes in Computer Science vol. 2274, pp. 280-296, Springer-Verlag, 2002.
Non-patent Document 3 (Document Joye-Tymenol): M. Joye, and C. Tymen, “Protections against differential analysis for elliptic curve cryptography”, Cryptographic Hardware and Embedded Systems 2001 (CHES2001), Lecture Notes in Computer Science vol. 2162, pp. 377-390, Springer-Verlag, 2001.
Non-patent Document 4 (Document Goubin03) L. Goubin, “A Refined Power-Analysis Attack on Elliptic Curve Cryptosystem”, Public-Key Cryptography 2003 (PKC2003), Lecture Notes in Computer Science vol. 2567, Springer-Verlag, pp. 199-210, 2003.
Non-patent Document 5 (Document Clavier-Joye01): C. Clavier, and M. Joye, “Universal exponentiation algorithm—A first step towards provable SPA-resistance—”, Cryptographic Hardware and Embedded Systems 2001 (CHES2001), Lecture Notes in Computer Science vol. 2162, Springer-Verlag, pp. 300-308, 2001.